【基础算法】刷题记录 2018-04-23

发表于
字数统计: 457 字 | 阅读时长 ≈ 2 分钟
  • 乘法表

乘法表（百度2016实习生真题）

题目描述

度度熊和爷爷在玩一个乘法表游戏。乘法表的第i行第j列位置的元素为$i*j$，并且乘法表下标编号从1开始，比如2 × 3乘法表为
1 2 3
2 4 6
爷爷十分聪明，对于nm的乘法表，只要度度熊给出一个数k，爷爷就能立刻告诉度度熊乘法表中元素按照不减顺序排列之后，第k个元素是多少。你能重复这个游戏吗？

输入

输入数据是三个整数：n, m, k (1≤n, $m≤5*10^5$, 1≤k≤nm)。

输出

输出n*m乘法表按照不减顺序排列的第k个数。

样例输入

2 3 4

样例输出

3

时间限制

C/C++语言：1000MS其它语言：3000MS

内存限制

C/C++语言：65536KB其它语言：589824KB

考点

  • 二分查找法
  • 巧算某个数在乘法表中是第几个数：对于每一列,如果k>=最后一个元素时，<=k的元素个数 = 总列数，否则个数 = k/行号，比如：n=6,m=3,k=6时，<=k的元素个数为：6+6/2+6/3 = 11
  • long long 数据类型： 1≤n, m≤5*10^5，则nm超过了int或long的范围，得用long long数据类型。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;
long long count(long long x, long long n, long long m){
	long long count = 0;
	for(long long i=1; i<=n;i++){
		if(x/i>m){
			count += m;
		}else{
			count += x/i;
		}
	}
	return count;
}
int main(){
	long long n,m;
	long long k;
	while(cin>>n>>m>>k){
		long long left = 1;
		long long right = n*m;
		//cout<<right<<endl;
		long long middle = (left+right)/2;
		while(left<=right){
		    //cout<<count(middle,n,m)<<endl;
			if(count(middle,n,m)>=k && count(middle-1,n,m)<k){
                cout<<middle<<endl;
				return 0;
			}else if(count(middle,n,m)<k){
				left = middle + 1;
				middle = (left + right) / 2;
			}else{
				right = middle - 1;
				middle = (left+right)/2;
			}
		}
	}
}